#include<stdlib.h>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=1e5;
struct node{
    int area;
    int data;
    int next;
    int num=2*maxn;
}inp[maxn];

bool exist[maxn];
bool cmp(node a,node b){
    return a.num<b.num;
}

int main(){
    int start,n,cnt1=0,cnt2=0,area;
    scanf("%d %d",&start,&n);
    for(int i=0;i<n;i++){
        scanf("%d",&area);
        scanf("%d %d",&inp[area].data,&inp[area].next);
        inp[area].area=area;
    }
    for(int i=start;i!=-1;i=inp[i].next){
        if(exist[abs(inp[i].data)]==false){
            exist[abs(inp[i].data)]=true;
            inp[i].num=cnt1++;
        }
        else{
            inp[i].num=maxn+cnt2;
            cnt2++;
        }
    }
    sort(inp,inp+maxn,cmp);
    int cnt=cnt1+cnt2;
    for(int i=0;i<cnt;i++){
        if(i!=cnt1-1&&i!=cnt-1){
            printf("%05d %d %05d\n",inp[i].area,inp[i].data,inp[i+1].area);
        }
        else{
            printf("%05d %d -1\n",inp[i].area,inp[i].data);
        }
    }
}
